1. Field of the Invention
The present invention relates to hardware for performing a table lookup in a large relatively sparse lookup table with limited types of entries.
2. State of the Art
With the advent of inexpensive high performance processors, a growing number of applications are using standard RISC processors to perform dedicated tasks within non-computing products. In many applications these embedded processors"" most frequent task is to access large external memory arrays. External memory can take anywhere from four to tens of system clock cycles to access. As a result, these repetitious xe2x80x9ctable lookupxe2x80x9d functions have become the activity which limits the performance of the products they are embedded in. It has become possible to create single semiconductor integrated circuits which incorporate the processor and some amount of memory. An on-chip memory access can take as little as two clock cycles, so for small lookup tables, a much faster single chip implementation is feasible. Unfortunately, if the application requires a large lookup table, the memory and processor cannot be integrated into a single chip.
If the table never changes, such as the case where the table that is accessed is contained in a Read Only Memory (ROM), and the data contained in the ROM is relatively sparse, i.e. contains many repeating values or empty entries, then the ROM could be converted into random logic and integrated into a single chip with the processor, since the amount of logic would be far smaller than the silicon area required for the ROM. The logic synthesis technique for doing this is well known, and tools exist to do this conversion automatically.
This hard-wired logic approach will not work if the data changes. Many applications, most notably networking routers, have data in large tables, in this case routing directories, which may change every few minutes. Reconfigurable logic on the other hand, is designed to be frequently updated, so reconfigurable logic could be used to contain the lookup table information. One example of reconfiguration logic is a PLA (Programmable Logic Array). FIG. 3a shows the AND/OR planes of a PLA, while FIG. 3b shows a typical horizontal input line driving an n-channel transistor connected to an AND line and GROUND. The output and line is charged up and any of the transistors in the column can pull the entire vertical wire low.
Most programmable logic solutions require hundreds of milliseconds to reprogram. Unfortunately, in many applications, the memory must be read frequently, which eliminates the ability to reconfigure it without unacceptably interrupting service. Furthermore, it usually takes a number of hours to place and route a new design in programmable logic, so the new changes would take a long time to incorporate.
A problem addressed by the present invention is shown in the prior art of FIG. 2. In this case, a processor looks up data in an external memory to translate information coming into a chip from one IO bus (the arrow pointing in) and then send it out (the arrow pointing out) to another external IO bus. This operation requires four external bus operations, and the processor must wait for the memory to return the proper value.
The present invention, generally speaking, provides hardware speedup for a table lookup operation. In an exemplary embodiment, a processor is integrated with a special type of reconfigurable logic. Preferably, the reconfigurable logic has the feature of being both partially and fully reconfigurable as necessary. The partial reconfiguration can be used to update the tables while in full operation, and the full reconfiguration can be done when it is necessary to reorganize the entire lookup table. This approach has the advantage of flexibility and speed which the other options lack.